//
//  SuffixTree.swift
//  Reader
//
//  Created by wsg on 2023/12/8.
//

import Foundation
class SuffixTreeNode {
    var children: [Character: SuffixTreeNode] = [:]
    var suffixIndex: Int?
    
    init() {}
}

class SuffixTree {
    private var root: SuffixTreeNode
    
    init() {
        root = SuffixTreeNode()
    }
    
    func buildTree(from text: String) {
        for i in 0..<text.count {
            insertSuffix(text, i)
        }
    }
    
    private func insertSuffix(_ text: String, _ suffixIndex: Int) {
        var currentNode = root
        
        for i in suffixIndex..<text.count {
            let currentChar = text[text.index(text.startIndex, offsetBy: i)]
            
            if let child = currentNode.children[currentChar] {
                currentNode = child
            } else {
                let newChild = SuffixTreeNode()
                currentNode.children[currentChar] = newChild
                currentNode = newChild
            }
        }
        
        currentNode.suffixIndex = suffixIndex
    }
    
    func findLongestCommonSubstring(strings: [String]) -> String {
        guard !strings.isEmpty else { return "" }
        
        // 构建后缀树
        for text in strings {
            buildTree(from: text)
        }
        
        // 寻找最长公共子串
        var longestCommonSubstring = ""
        findLongestCommonSubstring(root, &longestCommonSubstring, strings)
        
        return longestCommonSubstring
    }
    
    private func findLongestCommonSubstring(_ node: SuffixTreeNode, _ result: inout String, _ strings: [String]) {
        var childSuffixIndices: [Int] = []
        
        // 收集所有子节点的后缀索引
        for child in node.children.values {
            if let suffixIndex = child.suffixIndex {
                childSuffixIndices.append(suffixIndex)
            } else {
                // 递归处理子节点
                findLongestCommonSubstring(child, &result, strings)
            }
        }
        
        // 判断是否为公共节点
        if childSuffixIndices.count == strings.count {
            childSuffixIndices.sort()
            
            // 计算公共子串长度
            let commonSubstringStartIndex = childSuffixIndices[0]
            let commonSubstringEndIndex = childSuffixIndices[childSuffixIndices.count - 1]
            
            let startIndex = strings[0].index(strings[0].startIndex, offsetBy: commonSubstringStartIndex)
            let endIndex = strings[0].index(strings[0].startIndex, offsetBy: commonSubstringEndIndex + 1)
            let commonSubstring = String(strings[0][startIndex..<endIndex])
            
            // 更新最长公共子串
            if commonSubstring.count > result.count {
                result = commonSubstring
            }
        }
    }
}
